package com.practice.niuke.new_direct_practice.class19;

/**
 * 给定一个二维数组matrix， 每个单元都是一个整数， 有正有负。 最开始的时候小Q操纵 一条
 * 长度为0的蛇蛇从矩阵最左侧任选一个单元格进入地图， 蛇每次只能够到达当前位 置的右上
 * 相邻， 右侧相邻和右下相邻的单元格。 蛇蛇到达一个单元格后， 自身的长度会 瞬间加上该单
 * 元格的数值， 任何情况下长度为负则游戏结束。 小Q是个天才， 他拥有一 个超能力， 可以在
 * 游戏开始的时候把地图中的某一个节点的值变为其相反数(注:最多 只能改变一个节点)。 问
 * 在小Q游戏过程中， 他的蛇蛇最长长度可以到多少?
 * 比如:
 * 1 -4 10
 * 3 -2 -1
 * 2 -1 0
 * 0 5 -2
 * 最优路径为从最左侧的3开始， 3 -> -4(利用能力变成4) -> 10。 所以返回17。
 */
public class Code02_SnakeGame {

    public static int walk1(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                int[] ans = process(matrix, i, j);
                res = Math.max(res, Math.max(ans[0], ans[1]));
            }
        }
        return res;
    }

    // 从左侧到达(i,j)的旅程中
    // 0) 在没有使用过能力的情况下，返回路径最大和
    // 1) 在使用过能力的情况下，返回路径最大和
    public static int[] process(int[][] m, int i, int j) {
        if (j == 0) { // (i,j)就是最左侧的位置
            return new int[]{m[i][j], -m[i][j]};
        }
        // (i,j)的左侧有之前的路
        // 第一条路
        int[] preAns = process(m, i, j - 1);
        int preUnuse = preAns[0];
        int preUse = preAns[1];
        if (i - 1 >= 0) {
            preAns = process(m, i - 1, j - 1);
            preUnuse = Math.max(preUnuse, preAns[0]);
            preUse = Math.max(preUse, preAns[1]);
        }
        if (i + 1 < m.length) {
            preAns = process(m, i + 1, j - 1);
            preUnuse = Math.max(preUnuse, preAns[0]);
            preUse = Math.max(preUse, preAns[1]);
        }
        // preUnuse  之前旅程，没用过能力
        // preUse    之前旅程，已经使用过能力了
        int no = -1; // 之前没使用过能力，当前位置也不使用能力，的最优解
        int yes = -1; // 不管是之前使用能力，还是当前使用了能力，请保证能力只使用一次，最优解
        if (preUnuse >= 0) {
            no = m[i][j] + preUnuse;
            yes = -m[i][j] + preUnuse;
        }
        if (preUse >= 0) {
            yes = Math.max(yes, m[i][j] + preUse);
        }
        return new int[]{no, yes};
    }

    public static int walk2(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int[][][] dp = new int[matrix.length][matrix[0].length][2];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0][0] = matrix[i][0];
            dp[i][0][1] = -matrix[i][0];
            max = Math.max(dp[i][0][0], dp[i][0][1]);
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                int preUnuse = dp[i][j - 1][0];
                int preUse = dp[i][j - 1][1];
                if (i - 1 >= 0) {
                    preUnuse = Math.max(preUnuse, dp[i - 1][j - 1][0]);
                    preUse = Math.max(preUse, dp[i - 1][j - 1][1]);
                }
                if (i + 1 < matrix.length) {
                    preUnuse = Math.max(preUnuse, dp[i + 1][j - 1][0]);
                    preUse = Math.max(preUse, dp[i + 1][j - 1][1]);
                }
                dp[i][j][0] = -1;
                dp[i][j][1] = -1;
                if (preUnuse >= 0) {
                    dp[i][j][0] = matrix[i][j] + preUnuse;
                    dp[i][j][1] = -matrix[i][j] + preUnuse;
                }
                if (preUse >= 0) {
                    dp[i][j][1] = Math.max(dp[i][j][1], matrix[i][j] + preUse);
                }
                max = Math.max(max, Math.max(dp[i][j][0], dp[i][j][1]));
            }
        }
        return max;
    }

    public static String getString(int num) {
        String str = String.valueOf(num);
        if (str.length() == 1) {
            return " " + str;
        }
        return str;
    }

    public static class Info {
        /**
         * 不用能力时的最优长度
         */
        public int noBest;

        /**
         * 使用能力时的最优长度
         */
        public int yesBest;

        public Info(int noBest, int yesBest) {
            this.noBest = noBest;
            this.yesBest = yesBest;
        }
    }

    /**
     * 蛇选择最优的开始位置，以最优的走法(最合适的时机使用能力)，最终来到（i, j）位置停止
     * （1）最合适的时机使用过能力的情况下，能够走出的最大长度 yesBest；
     * （2）一次能力也没用过的情况下，走出的最大长度 noBest
     * 如果noBest，或者yesBest，哪个为负数，就认为改方案不存在。
     *
     * @param matrix 矩阵
     * @param i 最终来到(i, j)位置
     * @param j 最终来到(i, j)位置
     * @return Info
     */
    public static Info f(int[][] matrix, int i, int j) {
        if (j == 0) {// 说明(i, j)位置是最左侧的位置（最左列）
            // 不用能力的长度为matrix[i][j]
            // 使用能力的长度为-matrix[i][j]
            return new Info(matrix[i][j], -matrix[i][j]);
        }

        // 代码能走到这里说明，(i, j)位置不在最左侧（最左列）

        int noBest = -1;
        int yesBest = -1;

        // 之前的位置可能是左上角，左侧，左下角

        Info leftUp = null;
        Info left = null;
        Info leftDown = null;
        if (i - 1 >= 0) {// 有左上角的位置
            leftUp = f(matrix, i - 1, j - 1);
        }
        // 有左侧的位置
        left = f(matrix, i, j - 1);
        if (i + 1 < matrix.length) {// 有左下角的位置
            leftDown = f(matrix, i + 1, j - 1);
        }

        // 计算noBest
        if (leftUp != null && leftUp.noBest > 0){
            // leftUp.noBest > 0 说明有“到左上角还没有使用过能力”这种方案
            noBest = leftUp.noBest + matrix[i][j];
            // leftUp.noBest > 0 也说明来到（i, j）左上角不使用能力能活下来，在（i, j）位置可以使用能力
            yesBest = leftUp.noBest - matrix[i][j];
        }
        if (left != null && left.noBest > 0){
            // left.noBest > 0 说明有“到左侧还没有使用过能力”这种方案
            noBest = Math.max(noBest, left.noBest + matrix[i][j]);
            // left.noBest > 0 也说明来到（i, j）左侧不使用能力能活下来，在（i, j）位置可以使用能力
            yesBest = Math.max(yesBest, left.noBest - matrix[i][j]);
        }
        if (leftDown != null && leftDown.noBest > 0){
            // leftDown.noBest > 0 说明有“到左下角还没有使用过能力”这种方案
            noBest = Math.max(noBest, leftDown.noBest + matrix[i][j]);
            // leftDown.noBest > 0 也说明来到（i, j）左下角不使用能力能活下来，在（i, j）位置可以使用能力
            yesBest = Math.max(yesBest, leftDown.noBest - matrix[i][j]);
        }

        // 计算yesBest，来到（i,j）位置的时候，使用了一次能力
        // (1)之前用了，此时（i, j）不能用
        // (2)之前没用(leftUp.noBest > 0 活下来，left.noBest > 0 活下来，leftDown.noBest > 0 活下来)，此时（i, j）使用

        if (leftUp != null && leftUp.yesBest > 0){
            // leftUp.yesBest > 0 说明来到（i, j）左上角时使用了能力并能活下来，在（i, j）位置不能使用能力
            yesBest = Math.max(yesBest, leftUp.yesBest + matrix[i][j]);
        }
        if (left != null && left.yesBest > 0){
            yesBest = Math.max(yesBest, left.yesBest + matrix[i][j]);
        }
        if (leftDown != null && leftDown.yesBest > 0){
            yesBest = Math.max(yesBest, leftDown.yesBest + matrix[i][j]);
        }
        return new Info(noBest, yesBest);
    }


    public static void main(String[] args) {
        int[][] matrix = {
                {-100, -4000, -10000},
                {-200, -2000, -100000},
                {-300, -1000, -60000},
                {-2000, -5000, -20000000}};
        System.out.println(walk1(matrix));
        System.out.println(walk2(matrix));
    }

}
